/**
 * "m??*ss*?i*pi" 将生成下面的结构
 * parts = [
 *     { char: 'm', pos: [ 0 ], len: 1, firstOne: 1 }, // <- 这里 pos 只能为 [0]，因为他是正则的第一个部分，且不是 *（不定长）
 *     { char: '?', pos: [], len: 2, firstOne: 3 },
 *     { char: '*', pos: [], firstOne: 3 },
 *     { char: 'ss', pos: [ / * 3 (上面 firstOne 是 3 所以这里排除了) * /,5 ], len: 2, firstOne: 7 },
 *     { char: '*', pos: [], firstOne: 7 },
 *     { char: '?', pos: [], len: 1, firstOne: 8 },
 *     { char: 'i', pos: [ 10 ], len: 1, firstOne: 11 },
 *     { char: '*', pos: [], firstOne: 11 },
 *     { char: 'pi', pos: [], len: 2, firstOne: 0 }
 * ]
 * */
let makeParts = (p => {
    let lastOneAlp = 0;
    let parts = [];
    let t = '';
    p = p.replace(/[\*]+/g,'*');
    p.split('').forEach(ps => {
        if (ps === '*') {
            if (t) {
                parts.push({
                    char: t,
                    pos: []
                });
                t = '';
            }
            if (parts.length && parts[parts.length - 1].char === '*') {
            } else {
                // parts.push('*');
                parts.push({
                    char: '*',
                    pos: []
                });
            }
        } else if (ps === '?') {
            if (t) {
                parts.push({
                    char: t,
                    pos: []
                });
                t = '';
            }
            if (parts.length && parts[parts.length - 1].char === '?') {
                parts[parts.length - 1].len++;
            } else {
                // parts.push('*');
                parts.push({
                    char: '?',
                    pos: [],
                    len: 1
                });
            }
        } else {
            t += ps;
        }
    });
    if (t) {
        parts.push({
            char: t,
            pos: []
        });
        t = '';
    }
    parts = parts.map((_,ind) => {
        if (_.char !== '*' && _.char !== '?') {
            lastOneAlp = ind;
            _.len = _.char.length;
            _.firstOne = 0;
            return _;
        } else {
            _.firstOne = 0;
            return _;
        }
    });
    return {
        parts,lastOneAlp
    };
});

/**
 * s = 'acdcb',p = 'a*c?b'
 * [
 *     { char: 'a', pos: [ 0 ], len: 1, firstOne: 1 },
 *     { char: '*', pos: [], firstOne: 1 },
 *     { char: 'c', pos: [ 1, 3 ], len: 1, firstOne: 2 },
 *     { char: '?', pos: [], len: 1, firstOne: 3 },
 *     { char: 'b', pos: [ 4 ], len: 1, firstOne: 5 }
 * ]
 * */
let buildIndex = (parts,s) => {
    let over = false;
    parts.forEach((part,pind) => {
        if (over) {
            return;
        }
        if (part.char === '?') {
            if (pind) {
                parts[pind].firstOne = parts[pind - 1].firstOne + part.len;
            } else {
                parts[pind].firstOne = part.len;
            }
        } else if (part.char === '*') {
            if (pind) {
                parts[pind].firstOne = parts[pind - 1].firstOne;
            }
        } else {
            let ind = -1;
            do {
                ind = s.indexOf(part.char,ind + 1);
                if (ind !== -1) {
                    part.pos.push(ind);
                } else {
                    break;
                }
            } while (true);

            // 去除冗余计算
            if (pind) {
                let firstOne = parts[pind - 1].firstOne || 0;
                part.pos = part.pos.filter(_ => _ >= firstOne);
                if (part.pos.length) {
                    parts[pind].firstOne = part.pos[0] + part.len;
                    parts[pind].pos = part.pos;
                } else {
                    over = true;
                    parts[pind].pos = [];
                }
            } else {
                if (part.pos.length) {
                    parts[pind].firstOne = part.pos[0] + part.len;
                } else {
                    over = true;
                }
            }
        }
    });
    console.log(parts);
    return {
        parts,
        over
    }
};

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
    // 排除一些比较明显的情况
    if (s === p) {
        return true;
    }
    if (/^[\*]+$/g.test(p)) {
        return true;
    }
    if (s !== "" && p === "") {
        return false;
    }

    let {parts,lastOneAlp} = makeParts(p);

    // s = "aaaxxxxx" p = "bbbxxxx"
    if (parts[0].char !== '*' && parts[0].char !== '?') {
        if (!s.startsWith(parts[0].char)) {
            return false;
        }
    }
    let ps = parts.length - 1;
    // s = "aaaxxxxxbbb" p = "aaaxxxxaaa"
    if (parts[ps].char !== '*' && parts[ps].char !== '?') {
        if (!s.endsWith(parts[ps].char)) {
            return false;
        }
    }

    // let over = false;
    let obj = buildIndex(parts,s);
    if (obj.over) {
        return false;
    }
    parts = obj.parts;

    let next = true; // 是否必须紧跟
    let sLen = s.length;
    let search = (ind,cur) => {
        if (ind === parts.length) {
            // 检查是否满足要求
            if (parts[0].char === '*') {}
            if (!next) {
                if (cur <= s.length) {
                    return true;
                } else {
                    return false;
                }
            } else {
                if (cur === s.length) {
                    return true;
                }
            }
            return false;
        } else {
            let part = parts[ind];
            if (part.char === '?') {
                next = true;
                return search(ind + 1,cur + part.len);
            } else if (part.char === '*') {
                next = false;

                if (cur === sLen || ind === parts.length - 1) {
                    return search(ind + 1,cur);
                }

                let t = sLen;
                if (parts[ind + 1]) {
                    if (parts[ind + 1].char !== '?') {
                        t = parts[ind + 1].pos[parts[ind + 1].pos.length - 1] + 1;
                        let tt = parts[lastOneAlp].pos[parts[lastOneAlp].pos.length - 1] + 1;
                        if (t > tt) {
                            t = tt;
                        }
                    }
                }
                let ok = false;
                for (let i = cur;i < t;i++) {
                    ok = search(ind + 1,i);
                    if (ok) {
                        return ok;
                    }
                }
                return ok;
            } else {
                let pl = part.pos.length;
                if (!ind) {
                    if (part.pos[0] !== 0) {
                        return false;
                    } else {
                        return search(ind + 1,part.len);
                    }
                } else {
                    let ok = false;
                    for (let i = 0;i < pl;i++) {
                        if (ok) {
                            return ok;
                        }
                        if (next) {
                            if (part.pos[i] === cur) {
                                return search(ind + 1,cur + part.len);
                            } else if (part.pos[i] > cur) {
                                return false;
                            }
                        } else {
                            if (part.pos[i] >= cur) {
                                next = true;
                                ok = search(ind + 1,part.pos[i] + part.len);
                                next = false;
                            }
                        }
                    }
                    return ok;
                }
            }
        }
    };
    return search(0,0);
};

module.exports = {
    isMatch
}
